package com.zhu.algorithm.jzOffer.linkedList;

import java.util.HashMap;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zhujiabao
 * @Date: 2023/01/27/23:13
 * @Description: JZ35 复杂链表的复制
 */
public class Solution35 {


    public static void main(String[] args) {
//        构建链表
        RandomListNode headNode = new RandomListNode(0);
        RandomListNode listNode = headNode;
        for (int i = 1; i < 10; i++) {
            listNode.next = new RandomListNode(i);
            listNode = listNode.next;
        }

        Solution35 solution35 = new Solution35();

        solution35.printLinklist(headNode);

        solution35.printLinklist(solution35.Clone(headNode));
        
    }

    public RandomListNode Clone(RandomListNode pHead) {

        if (pHead == null) {
            return null;
        }

        HashMap<RandomListNode, RandomListNode> hashMap = new HashMap<>();
        RandomListNode newHeadNode;
        RandomListNode newListNode;
        RandomListNode oldListNode = pHead;
        newHeadNode = newListNode = new RandomListNode(oldListNode.label);
        hashMap.put(pHead, newHeadNode);
        while (oldListNode.next != null) {
            oldListNode = oldListNode.next;
            newListNode.next = new RandomListNode(oldListNode.label);
            newListNode = newListNode.next;
            hashMap.put(oldListNode, newListNode);
        }

        oldListNode = pHead;
        newListNode = newHeadNode;
        newHeadNode.random = hashMap.get(pHead.random);
        while (oldListNode.next != null) {
            oldListNode = oldListNode.next;
            newListNode.next.random = hashMap.get(oldListNode.random);
            newListNode = newListNode.next;
        }
        return newHeadNode;
    }



    // 打印链表
    public void printLinklist(RandomListNode HeadList) {
        RandomListNode listNode = HeadList;
        System.out.print("[ ");
        while (listNode != null) {
            System.out.print(listNode.label + ", ");
            listNode = listNode.next;
        }
        System.out.println(" ]");
    }
}
